// https://www.lintcode.com/problem/fast-power

public class Solution {
    /**
     * @param a: A 32bit integer
     * @param b: A 32bit integer
     * @param n: A 32bit integer
     * @return: An integer
     */
    public int fastPower(int a, int b, int n) {
        // write your code here
        if (n == 0) {
            return 1 % b;
        } else if (n == 1) {
            return a % b;
        } else {
            long x = fastPower(a, b, n / 2);
            if ((n % 2) == 1) {
                return (int)((((x * x) % b) * a) % b);
            } else {
                return (int)((x * x) % b);
            }
        }
    }
}